package com.heima.leetcode.practice;

/**
 * leetcode 2. 两数相加
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/7 10:27
 */
public class E2 {

    /**
     * <h3>方法一：递归法1</h3>
     * @param list1 链表存储的数字1
     * @param list2 链表存储的数字2
     * @return 相加后的结果的链表
     */
    public ListNode addTwoNumbers1(ListNode list1, ListNode list2) {
        return addTwoNumbers1(list1, list2, false);
    }

    /**
     * 递归实现
     * @param list1 链表1当前的节点
     * @param list2 链表2当前的节点
     * @param isCarry 是否进位
     * @return 相加后的链表
     */
    private ListNode addTwoNumbers1(ListNode list1, ListNode list2, boolean isCarry) {
        // 递归结束条件：有一个为链表处理完了
        if (list1 == null && list2 == null){ // 两个位都是null
            return isCarry ? new ListNode(1) : null;
        } else if (list1 == null) {
            if (isCarry) { // 有进位的情况可能会遇到后面9999的情况
                int sum = list2.val + 1;
                isCarry = sum == 10; // 更新是否进位
                sum = isCarry ? 0 : sum; // 更新sum值
                ListNode curr = new ListNode(sum);
                curr.next = addTwoNumbers1(null, list2.next, isCarry); // 递归处理后面位
                return curr;
            }
            return list2;
        } else if (list2 == null) {
            if (isCarry){
                int sum = list1.val + 1;
                isCarry = sum == 10; // 更新是否进位
                sum = isCarry ? 0 : sum; // 更新sum值
                ListNode curr = new ListNode(sum);
                curr.next = addTwoNumbers1(list1.next, null, isCarry); // 递归处理后面位
                return curr;
            }
            return list1;
        } else {
            // 递的时候相加当前位，并判断是否进位，如果当前位两个链表都有值，进行递的操作
            int sum = list1.val + list2.val + (isCarry ? 1 : 0);
            isCarry = sum >= 10; // 更新是否要向下一位进位
            sum = isCarry ? sum - 10 : sum; // 如果要向下一位进位，更新sum值
            ListNode curr = new ListNode(sum);
            // 归的时候返回当前节点以后的链表
            curr.next = addTwoNumbers1(list1.next, list2.next, isCarry);
            return curr;
        }
    }

    /**
     * <h3>方法二：递归法2，对方法一的优化，效率最高</h3>
     * @param list1 链表存储的数字1
     * @param list2 链表存储的数字2
     * @return 相加后的结果的链表
     */
    public ListNode addTwoNumbers2(ListNode list1, ListNode list2) {
        return addTwoNumbers2(list1, list2, false);
    }

    /**
     * 递归实现，优化
     * @param list1 链表1当前的节点
     * @param list2 链表2当前的节点
     * @param isCarry 是否进位
     * @return 相加后的链表
     */
    private ListNode addTwoNumbers2(ListNode list1, ListNode list2, boolean isCarry) {
        // 递归结束条件：两个链表都处理完了
        if (list1 == null && list2 == null){
            return isCarry ? new ListNode(1) : null;
        }
        // 递的时候当前位相加，如果一个链表要短写，当前位有一个是null当0处理
        int value1 = list1 == null ? 0 : list1.val;
        int value2 = list2 == null ? 0 : list2.val;
        ListNode next1 = list1 == null ? null : list1.next;
        ListNode next2 = list2 == null ? null : list2.next;

        int carry = isCarry ? 1 : 0;
        int sum = value1 + value2 + carry;
        isCarry = sum >= 10;
        sum = isCarry ? sum - 10 : sum;

        // 创建当前节点
        ListNode node = new ListNode(sum);
        // 递归处理下一个节点，归的时候将结果链表串起来
        node.next = addTwoNumbers2(next1, next2, isCarry);
        return node;
    }

    /**
     * <h3>方法三：双指针法</h3>
     * @param list1 链表存储的数字1
     * @param list2 链表存储的数字2
     * @return 相加后的结果的链表
     */
    public ListNode addTwoNumbers3(ListNode list1, ListNode list2) {
        ListNode sentinel = new ListNode(-1); // 哨兵节点
        ListNode curr = sentinel; // 当前节点
        int carry = 0; // 进位，每位都会有进位，要么0要么1
        while (list1 != null || list2 != null){ // 只要有一个链表还有值，就继续循环
            int value1 = list1 == null ? 0 : list1.val; // 链表1当前位，如果为null，当0处理
            int value2 = list2 == null ? 0 : list2.val; // 链表2当前位，如果为null，当0处理
            ListNode next1 = list1 == null ? null : list1.next; // 当前节点为null，下一个节点当null处理
            ListNode next2 = list2 == null ? null : list2.next; // 当前节点为null，下一个节点当null处理

            int sum = value1 + value2 + carry; // 当前位和进位相加
            carry = sum >= 10 ? 1 : 0; // 更新向下一位的进位
            sum = carry == 1 ? sum - 10 : sum; // 更新当前位的值

            curr.next = new ListNode(sum); // 创建当前节点
            curr = curr.next; // 移动到当前结果节点
            list1 = next1; // list1移动到下一个节点
            list2 = next2; // list2移动到下一个节点
        }
        curr.next = carry == 1 ? new ListNode(1) : null; // 当最后一位有进位，创建一个1节点，否则为null
        return sentinel.next; // 返回结果链表
    }

    /**
     * <h3>方法四：双指针法，优化</h3>
     * @param l1 链表1
     * @param l2 链表2
     * @return 相加后的链表
     */
    public ListNode addTwoNumbers4(ListNode l1, ListNode l2) {
        ListNode sentinel = new ListNode();
        ListNode curr = sentinel;
        int carray = 0;
        while(l1 != null || l2 != null || carray != 0){
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;

            int sum = v1 + v2 + carray;
            carray = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum - 10 : sum;

            curr.next = new ListNode(sum);
            curr = curr.next;

            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        return sentinel.next;
    }
}
